package leetcode.pre50;

import utils.ListNode;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * {@link baseclass.d_list.Code09_MergeTwoSortedList}
 * {@link baseclass.d_list.Code09_MergeKSortedList}
 * {@link baseclass.a_sort.mergeSort.MergeSort}
 * @date 2020/3/24 15:11
 */
public class Code23_MergeKSortedList {
    public ListNode mergeKLists1(ListNode[] lists) {
        if(lists == null || lists.length == 0)return null;
        Queue<ListNode> minQ = new PriorityQueue<>((l1,l2) -> l1.val - l2.val);
        //把每个链表的头部放入
        for (ListNode listHead : lists) {
            //注意这里一定要判断，因为可能是[[1,2],[]]
            if(listHead != null)
                minQ.add(listHead);
        }
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        //遍历
        while (!minQ.isEmpty()){
            //找到所属链表
            ListNode poll = minQ.poll();
            cur.next = poll;
            cur = cur.next;
            if(poll.next != null){
                minQ.add(poll.next);
            }
        }
        return head.next;
    }
    public ListNode mergeKLists2(ListNode[] lists) {
        if(lists == null || lists.length == 0)return null;
        return merge(lists,0,lists.length-1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if(left >= right) return lists[left];
        int mid = (left + right) >> 1;
        ListNode l1Head = merge(lists, left, mid);
        ListNode l2Head = merge(lists, mid + 1, right);
        return doMerge(l1Head,l2Head);
    }

    /**
     * 合并两个有序链表
     */
    private ListNode doMerge(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode node;
        if (l1.val < l2.val) {
            node = l1;
            node.next = doMerge(l1.next, l2);
        } else {
            node = l2;
            node.next = doMerge(l1, l2.next);
        }
        return node;
    }
}
